package com.suxin.algorithm.linked;

/**
 * @author Tang
 * @classname ReverseLinked
 * @description [
 * 链表反转： 1.递归法，2.头插法(会消耗额外的空间)
 * ]
 * @date 2022/4/1 14:17
 */
public class ReverseLinked {

    public Node createLink() {
        Node head = new Node(null);
        Node temp = head;
        for (int i = 0; i < 5; i++) {
            Node node = new Node(i);
            temp.next = node;
            temp = node;
        }
        return head.next;
    }

    /**
     * 反转链表: 递归方式
     * node: 在递归栈中代表是链表中的其中一个节点
     */
    public Node reverse(Node node) {
        // 递归出口,,返回最后一个节点,,
        if (node == null || node.next == null) {
            return node;
        }
        // 头节点
        Node head = reverse(node.next);
        // 反转开始,当前节点的下一个节点设置为当前节点
        node.next.next = node;
        // 断开当前节点的下一个引用，防止死循环
        node.next = null;
        return head;
    }

    public String print(Node head) {
        StringBuilder sb = new StringBuilder();
        Node cur = head;
        while (cur != null) {
            sb.append(cur.data).append("-->");
            cur = cur.next;
        }
        sb.append("NULL");
        return sb.toString();
    }

    public static void main(String[] args) {
        ReverseLinked linked = new ReverseLinked();
        Node node = linked.createLink();
        System.out.println("原始链表:" + linked.print(node));
        System.out.println("递归方式反转:" + linked.print(linked.reverse(node)));
    }

    private static class Node<T> {

        private T data;

        private Node next;

        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

}